package com.sfx.算法专题.排序.quicksort;

import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-09-04
 * Time: 8:04
 */
public class Code_2_quickSort {
    // 为什么 数据重复的时候,数组分为三块算法的效率较高 ?
    // 因为 当数据全部重复的时候,数组就会被划分为1块,再去划分左半部分和右半部分的时候
    // 左区间和右区间都不存在,所以算法效率较高一些.-->仅需执行一次快慢就结束了
    // 我们选择基准元素的时候,有三数取中,选最左边,选最右边,随机的方式
    // 但在算法导论中 算过概率,当我们使用随机的方式选择基准方式是最快的,算法时间复杂度逼近于logN
    // 0   10
    // 1  6
    // [0,10] + left
    // 1,11

    static class Solution {

        private Random rand = new Random();

        private void swap(int[] nums,int left,int right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }

        public void quickSort(int[] nums,int l,int r) {
            if(l >= r) return ;
            // 选择一个基准下标
            int key = nums[rand.nextInt(r - l + 1) + l];
            int i = l;
            int left = l - 1;
            int right = r + 1;
            // 左边都是<pivot的  右边都是>pivot的
            while(i < right) {
                if(nums[i] < key) {
                    swap(nums,++left,i++);
                }else if(nums[i] > key) {
                    swap(nums,--right,i);
                }else {
                    // ==
                    i++;
                }
            }
            //              pivot
            // [l,left] [left+1,right-1] [right,r]
            quickSort(nums,l,left);
            quickSort(nums,right,r);
        }

        public int[] sortArray(int[] nums) {
            quickSort(nums,0,nums.length-1);
            return nums;
        }
    }
}